cornellmaefandomcom-20200213-history
Optimization Algorithm
Let's suppose that you would like to optimize some objective function. There are many optimization algorithms and software to use, but there is no single algorithm that will work for all problems. Here is a list of some commonly used optimization routines, and the types of problems that they're good for solving. CVX * Matlab Toolbox, written by Stephen Boyd * Website: http://cvxr.com/cvx/ * Problem Requirements: ** Must be Convex * Comments: ** Good for simple and well posed problems. ** Good for solving Linear Matrix Inequality (LMI) problems SNOPT * Fortran Library, able to be called from Matlab and C++ * Website: http://web.stanford.edu/group/SOL/snopt.htm * Problem Requirements: ** Objective and Constraints must be smooth and consistent * Comments: ** MAE owns a department licence - contact Andy Ruina to get a copy ** SNOPT is considered by many to be to be the best non-linear smooth optimization program available ** Similiar to Matlab's FMINCON IPOPT * * Coments: ** Same class of solver as SNOPT, but less widely used FMINCON * Part of the Matlab Optimization Toolbox * Problem Requirements: ** Objective and Constraints must be smooth and consistent * Comments: ** Very similar to SNOPT Simulated Anealing * A general method for solving global optimization problems * Wikipedia: http://en.wikipedia.org/wiki/Simulated_annealing * Problem Requirements: ** Global Optimization ** No direct constraint handling (must be added to objective) ** Problem should have gradients, but they need not be perfectly smooth * Notes: ** Fairly easy to implement on your own ** Matlab has an implementation in the Global Optimization Toolbox ** This is good if you just want a quick answer to a poorly posed problem ** Good for multi-modal problems Covariance Matrix Adaptation - Evolutionary Strategy (CMAES) * An evolutionary-inspired method for solving difficult optimization problems * Website: https://www.lri.fr/~hansen/cmaesintro.html * Download: https://www.lri.fr/~hansen/cmaes_inmatlab.html * Problem Requirements: ** Global Optimization ** No direct constraint handling (must be added to objective) ** Problem should have gradients, but they need not be perfectly smooth ** Problem should be approximately uni-modal * Comments: ** Source code download is excellent for Matlab. Many other languages as well. ** Really good at solving problems that are not smooth, provided there is some gradient Trajectory Optimization * Trajectory optimization really has two parts: ** A transcription method - reformulates problem for a general solver. The general idea is to converge a low-dimensional non-linear problem into a high-dimensional problem that is nearly convex and nearly linear. Objective function must be smooth, or all hope is lost. *** Multiple Shooting *** Collocation ** A general non-linear constrained optimization method *** SNOPT, IPOPT, FMINCON * The best commercial solver is GPOPS2 (see below). * Implementing your own is tricky, but doable. GPOPS2 * Matlab Library * Website: http://www.gpops2.com/ * Problem Requirements: ** Must be Smooth and Consistent * Comments: ** Calls either IPOPT or SNOPT ** By far the best trajectory optimization method that I've seen ** Adaptive collocation method BVP4C and BVP5C * Matlab functions for solving boundary value problems